{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This is a sketch of the constrained decoding algorithm by Hokamp & Liu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "from collections import defaultdict, OrderedDict\n",
    "import numpy as np\n",
    "from sortedcontainers import SortedListWithKey"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# imagine a max_source_len x constraint_len+1 grid\n",
    "# at the top left corner, there is a triangle with constraint_len-1 sides cut out\n",
    "# at the bottom right corner, there is a triangle with constraint_len sides cut out\n",
    "\n",
    "# we move to the right, filling the beams in each column starting with the bottommost, and moving upwards\n",
    "#        - filling the beams in a column can be done in parallel, since there are no dependencies within the column\n",
    "\n",
    "# the horizontal (t) axis represents time\n",
    "#     - every hypothesis in a column t has the same number of tokens\n",
    "# the vertical axis (j) represents coverage of constraints\n",
    "#     - every hypothesis in a row j covers the same number of constraint tokens\n",
    "\n",
    "# FILLING CELL (i,j)\n",
    "# there are two source beams from which we can generate hypotheses:\n",
    "# LEFT (cell (i-1, j))\n",
    "#    - this cell can only generate \n",
    "# BELOW+LEFT (cell (i-1, j-1))\n",
    "#    - this cell can add constraints in two ways:\n",
    "#      (1) constraints which are unfinished _MUST_ be continued\n",
    "#      (2) new constraints can be started\n",
    "#    - hypotheses from this beam always update the constraint coverage\n",
    "\n",
    "# Generating constraint hypotheses\n",
    "# the hypothesis object holds all of the states needed to generate the n-best continuations at the next timestep\n",
    "# this is the purpuse of the `payload` attribute of hypothesis objects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NOTES:\n",
    "# without a special feature, generating a word and using the same word from a constraint have the same score,\n",
    "# thus we need a way to decide whether we are generating a word, or starting a new constraint which begins with \n",
    "# that word\n",
    "# - the constraint pointer model is one way of scoring hypotheses from the different sources differently"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocabulary = [0,1,2,3,4,5,6,7,8,9]\n",
    "\n",
    "sample_constraints = [\n",
    "    [1,2],\n",
    "    [5,6,7]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Thinking buffer\n",
    "def init_coverage(constraints):\n",
    "    coverage = []\n",
    "    for c in constraints:\n",
    "        coverage.append(np.zeros(len(c), dtype='int16'))\n",
    "    return coverage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ConstraintHypothesis:\n",
    "    \"\"\"A (partial) hypothesis which maintains an additional constraint coverage object\n",
    "    \n",
    "    Args:\n",
    "        token (unicode): the surface form of this hypothesis\n",
    "        score (float): the score of this hypothesis (higher is better)\n",
    "        coverage (list of lists): a representation of the area of the constraints covered by this hypothesis\n",
    "        constraints (list of lists): the constraints that may be used with this hypothesis\n",
    "        payload (:obj:): additional data that comes with this hypothesis. Functions may \n",
    "            require certain data to be present in the payload, such as the previous states, glimpses, etc...\n",
    "        backpointer (:obj:`ConstraintHypothesis`): a pointer to the hypothesis object which generated this one\n",
    "        constraint_index (tuple): if this hyp is part of a constraint, the index into `self.constraints` which\n",
    "            is covered by this hyp `(constraint_idx, token_idx)`\n",
    "        unfinished_constraint (bool): a flag which indicates whether this hyp is inside an unfinished constraint\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, token, score, coverage, constraints, payload=None, backpointer=None,\n",
    "                 constraint_index=None, unfinished_constraint=False):\n",
    "        self.token = token\n",
    "        self.score = score\n",
    "        \n",
    "        assert len(coverage) == len(constraints), 'constraints and coverage length must match'\n",
    "        assert all(len(cov) == len(cons) for cov, cons in zip(coverage, constraints)), \\\n",
    "            'each coverage and constraint vector must match'\n",
    "        \n",
    "        self.coverage = coverage\n",
    "        self.constraints = constraints\n",
    "        self.backpointer = backpointer\n",
    "        self.payload = payload\n",
    "        self.constraint_index = constraint_index\n",
    "        self.unfinished_constraint = unfinished_constraint\n",
    "        \n",
    "    def __str__(self):\n",
    "        return u'token: {}, sequence: {}, score: {}, coverage: {}, constraints: {},'.format(\n",
    "            self.token, self.sequence, self.score, self.coverage, self.constraints)\n",
    "    \n",
    "    def __getitem__(self, key):\n",
    "        return getattr(self, key)\n",
    "    \n",
    "    @property\n",
    "    def sequence(self):\n",
    "        sequence = []\n",
    "        current_hyp = self\n",
    "        while current_hyp.backpointer is not None:\n",
    "            sequence.append((current_hyp.token, current_hyp.constraint_index))\n",
    "            current_hyp = current_hyp.backpointer\n",
    "        sequence.append((current_hyp.token, current_hyp.constraint_index))\n",
    "        return sequence[::-1]\n",
    "    \n",
    "    def constraint_candidates(self):\n",
    "        available_constraints = []\n",
    "        for idx in range(len(self.coverage)):\n",
    "            if self.coverage[idx][0] == 0:\n",
    "                available_constraints.append(idx)\n",
    "            \n",
    "        return available_constraints\n",
    "    \n",
    "    \n",
    "        \n",
    "        \n",
    "class AbstractBeam():\n",
    "    \n",
    "    def __init__(self, size):\n",
    "        # note: here we assume bigger scores are better\n",
    "        self.hypotheses = SortedListWithKey(key=lambda x: -x['score'])\n",
    "        self.size = size\n",
    "    \n",
    "    def add(self, hyp):\n",
    "        self.hypotheses.add(hyp)\n",
    "        if len(self.hypotheses) > self.size:\n",
    "            assert len(self.hypotheses) == self.size + 1\n",
    "            del self.hypotheses[-1]\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.hypotheses)\n",
    "    \n",
    "    def __iter__(self):\n",
    "        for hyp in self.hypotheses:\n",
    "            yield hyp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# FUNCTIONS USED BY THE CONSTRAINED DECODER\n",
    "# Note: hyps on the top level may be finished (End with EOS), or may be continuing (haven't gotten an EOS yet)\n",
    "\n",
    "class ConstrainedDecoder(object):\n",
    "    \n",
    "    def __init__(self, hyp_generation_func, constraint_generation_func, continue_constraint_func,\n",
    "                 beam_implementation=AbstractBeam):\n",
    "        self.hyp_generation_func = hyp_generation_func\n",
    "        self.constraint_generation_func = constraint_generation_func\n",
    "        self.continue_constraint_func = continue_constraint_func\n",
    "        self.beam_implementation = beam_implementation\n",
    "        \n",
    "    # QUESTION: are mid-constraint hyps allowed to fall off of the beam or not?\n",
    "    def search(self, start_hyp, constraints, max_source_len, beam_size=10):\n",
    "        \"\"\"create a constrained search\n",
    "            - fill the search grid\n",
    "        \"\"\"\n",
    "        \n",
    "        # the total number of constraint tokens determines the height of the grid\n",
    "        grid_height = sum(len(c) for c in constraints)\n",
    "        \n",
    "        search_grid = OrderedDict()\n",
    "        \n",
    "        # a beam with one hyp starts the search\n",
    "        start_beam = self.beam_implementation(size=1)\n",
    "        start_beam.add(start_hyp)\n",
    "        \n",
    "        search_grid[(0,0)] = start_beam\n",
    "        \n",
    "        for i in range(1, max_source_len + 1):\n",
    "            print('TIME: {}'.format(i+1))\n",
    "            j_start = max(i - (max_source_len - grid_height), 0)\n",
    "            j_end = min(i, grid_height) + 1\n",
    "            beams_in_i = j_end - j_start\n",
    "            for j in range(j_start, min(i, grid_height) + 1):\n",
    "                # create the new beam\n",
    "                new_beam = self.beam_implementation(size=beam_size)\n",
    "                # generate hyps from (i-1, j-1), and (i-1, j), and add them to the beam\n",
    "                # cell to the left generates\n",
    "                if (i-1, j) in search_grid:\n",
    "                    generation_hyps = self.get_generation_hyps(search_grid[(i-1, j)])\n",
    "                    for hyp in generation_hyps:\n",
    "                        new_beam.add(hyp)\n",
    "                # lower left diagonal cell adds hyps from constraints\n",
    "                if (i-1, j-1) in search_grid:\n",
    "                    new_constraint_hyps = self.get_new_constraint_hyps(search_grid[(i-1, j-1)])\n",
    "                    continued_constraint_hyps = self.get_continued_constraint_hyps(search_grid[(i-1, j-1)])\n",
    "                    for hyp in new_constraint_hyps:\n",
    "                        new_beam.add(hyp)\n",
    "                    for hyp in continued_constraint_hyps:\n",
    "                        new_beam.add(hyp)\n",
    "                \n",
    "                search_grid[(i,j)] = new_beam\n",
    "            \n",
    "                print('index: {}'.format((i,j)))\n",
    "        \n",
    "        return search_grid\n",
    "    \n",
    "# FILLING CELL (i,j)\n",
    "# there are two source beams from which we can generate hypotheses:\n",
    "# LEFT (cell (i-1, j))\n",
    "#    - this cell can only generate \n",
    "# BELOW+LEFT (cell (i-1, j-1))\n",
    "#    - this cell can add constraints in two ways:\n",
    "#      (1) constraints which are unfinished _MUST_ be continued\n",
    "#      (2) new constraints can be started\n",
    "#    - hypotheses from this beam always update the constraint coverage\n",
    "    def get_generation_hyps(self, beam):\n",
    "        \"\"\"return all hyps which are continuations of the hyps on this beam\n",
    "    \n",
    "        hyp_generation_func maps `(hyp) --> continuations`\n",
    "    \n",
    "        the coverage vector of the parent hyp is not modified in each child\n",
    "        \"\"\"\n",
    "    \n",
    "        continuations = (self.hyp_generation_func(hyp) for hyp in beam if not hyp.unfinished_constraint)\n",
    "    \n",
    "        # flatten\n",
    "        return (new_hyp for hyp_list in continuations for new_hyp in hyp_list)\n",
    "        \n",
    "    def get_new_constraint_hyps(self, beam):\n",
    "        \"\"\"return all hyps which start a new constraint from the hyps on this beam\n",
    "    \n",
    "        constraint_hyp_func maps `(hyp) --> continuations`\n",
    "    \n",
    "        the coverage vector of the parent hyp is modified in each child\n",
    "        \"\"\"\n",
    "    \n",
    "        continuations = (self.constraint_generation_func(hyp)\n",
    "                         for hyp in beam if not hyp.unfinished_constraint)\n",
    "    \n",
    "        # flatten\n",
    "        return (new_hyp for hyp_list in continuations for new_hyp in hyp_list)\n",
    "\n",
    "\n",
    "    def get_continued_constraint_hyps(self, beam):\n",
    "        \"\"\"return all hyps which continue the unfinished constraints on this beam\n",
    "    \n",
    "        constraint_hyp_func maps `(hyp, constraints) --> forced_continuations`\n",
    "    \n",
    "        the coverage vector of the parent hyp is modified in each child\n",
    "\n",
    "        \"\"\"\n",
    "        continuations = (self.continue_constraint_func(hyp)\n",
    "                         for hyp in beam if hyp.unfinished_constraint)\n",
    "    \n",
    "        return continuations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the implementations of the generate, start_constraint, and continue_constraint functions depend upon the decoder\n",
    "\n",
    "# to generate, we query the decoder with a hypothesis\n",
    "# the decoder uses the payload to compute the next most probable continuations\n",
    "\n",
    "# to start new constrained hypotheses, we need to:\n",
    "# constrained_hyps = []\n",
    "# for constraint_idx in constraint_candidates(hyp):\n",
    "#     new_hyp = build_hyp(hyp, constraint_idx, constraints)\n",
    "#     constrained_hyps.append(new_hyp)\n",
    "\n",
    "\n",
    "# to continue a constrained hypothesis, we need to:\n",
    "# (1) find the constraint to continue via the coverage object\n",
    "# (2) find the next token in the constraint\n",
    "# (3) \n",
    "# (4) get the data for this token (score, states, etc...) -- i.e. forced decode for one step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "# DUMBEST POSSIBLE IMPLEMENTATION of generation functions\n",
    "# Note that generation and search are done by _different_ classes\n",
    "\n",
    "class DumbTranslationModel(object):\n",
    "    \n",
    "    def __init__(self, vocabulary):\n",
    "        self.vocabulary = vocabulary\n",
    "    \n",
    "    def dumb_generate(self, hyp, n_best=1):\n",
    "        # make k_best random hyp objects\n",
    "        next_tokens = np.random.choice(self.vocabulary, size=n_best)\n",
    "        next_scores = np.random.random(size=n_best)\n",
    "        \n",
    "        new_hyps = []\n",
    "        for i in range(n_best):\n",
    "            new_hyp = ConstraintHypothesis(token=next_tokens[i],\n",
    "                                           score=next_scores[i],\n",
    "                                           coverage=copy.deepcopy(hyp.coverage),\n",
    "                                           constraints=hyp.constraints,\n",
    "                                           payload=None,\n",
    "                                           backpointer=hyp,\n",
    "                                           constraint_index=None,\n",
    "                                           unfinished_constraint=False\n",
    "                                          )\n",
    "            new_hyps.append(new_hyp)\n",
    "        \n",
    "        return new_hyps\n",
    "    \n",
    "    def dumb_generate_from_constraints(self, hyp):\n",
    "        \"\"\"Look at the coverage of the hyp to get constraint candidates\"\"\"\n",
    "        \n",
    "        assert hyp.unfinished_constraint is not True, 'hyp must not be part of an unfinished constraint'\n",
    "        new_constraint_hyps = []\n",
    "        available_constraints = hyp.constraint_candidates()\n",
    "        for idx in available_constraints:\n",
    "            # starting a new constraint\n",
    "            constraint_token = hyp.constraints[idx][0]\n",
    "            # this should come from the model\n",
    "            score = np.random.random()\n",
    "            coverage = copy.deepcopy(hyp.coverage)\n",
    "            coverage[idx][0] = 1\n",
    "            if len(coverage[idx]) > 1:\n",
    "                unfinished_constraint = True\n",
    "            else:\n",
    "                unfinished_constraint = False\n",
    "                \n",
    "            new_hyp = ConstraintHypothesis(token=constraint_token,\n",
    "                                           score=score,\n",
    "                                           coverage=coverage,\n",
    "                                           constraints=hyp.constraints,\n",
    "                                           payload=None,\n",
    "                                           backpointer=hyp,\n",
    "                                           constraint_index=(idx, 0),\n",
    "                                           unfinished_constraint=unfinished_constraint\n",
    "                                          )\n",
    "            new_constraint_hyps.append(new_hyp)\n",
    "        \n",
    "        return new_constraint_hyps\n",
    "        \n",
    "    \n",
    "    def dumb_continue_unfinished_constraint(self, hyp):\n",
    "        assert hyp.unfinished_constraint is True, 'hyp must be part of an unfinished constraint'\n",
    "        \n",
    "        # this should come from the model\n",
    "        score = np.random.random()\n",
    "        \n",
    "        constraint_row_index = hyp.constraint_index[0]\n",
    "        # the index of the next token in the constraint\n",
    "        constraint_tok_index = hyp.constraint_index[1] + 1\n",
    "        constraint_index = (constraint_row_index, constraint_tok_index)\n",
    "        \n",
    "        continued_constraint_token = hyp.constraints[constraint_index[0]][constraint_index[1]]\n",
    "        \n",
    "        coverage = copy.deepcopy(hyp.coverage)\n",
    "        coverage[constraint_row_index][constraint_tok_index] = 1\n",
    "        \n",
    "        if len(hyp.constraints[constraint_row_index]) > constraint_tok_index + 1:\n",
    "            unfinished_constraint = True\n",
    "        else:\n",
    "            unfinished_constraint = False\n",
    "        \n",
    "        new_hyp = ConstraintHypothesis(token=continued_constraint_token,\n",
    "                                       score=score,\n",
    "                                       coverage=coverage,\n",
    "                                       constraints=hyp.constraints,\n",
    "                                       payload=None,\n",
    "                                       backpointer=hyp,\n",
    "                                       constraint_index=constraint_index,\n",
    "                                       unfinished_constraint=unfinished_constraint\n",
    "                                      )\n",
    "        return new_hyp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "START_TOKEN = u'<S>'\n",
    "P_START = 1.0\n",
    "N_BEST = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "dumb_tm = DumbTranslationModel(vocabulary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "decoder = ConstrainedDecoder(hyp_generation_func=dumb_tm.dumb_generate,\n",
    "                             constraint_generation_func=dumb_tm.dumb_generate_from_constraints,\n",
    "                             continue_constraint_func=dumb_tm.dumb_continue_unfinished_constraint,\n",
    "                             beam_implementation=AbstractBeam)\n",
    "\n",
    "#     def __init__(self, hyp_generation_func, constraint_generation_func, continue_constraint_func,\n",
    "#                  beam_implementation=AbstractBeam):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "start_hyp = ConstraintHypothesis(token=START_TOKEN, score=P_START,\n",
    "                                 coverage=init_coverage(sample_constraints),\n",
    "                                 constraints=sample_constraints,\n",
    "                                 payload=None,\n",
    "                                 backpointer=None,\n",
    "                                 unfinished_constraint=False\n",
    "                                )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TIME: 2\n",
      "index: (1, 0)\n",
      "index: (1, 1)\n",
      "TIME: 3\n",
      "index: (2, 0)\n",
      "index: (2, 1)\n",
      "index: (2, 2)\n",
      "TIME: 4\n",
      "index: (3, 0)\n",
      "index: (3, 1)\n",
      "index: (3, 2)\n",
      "index: (3, 3)\n",
      "TIME: 5\n",
      "index: (4, 0)\n",
      "index: (4, 1)\n",
      "index: (4, 2)\n",
      "index: (4, 3)\n",
      "index: (4, 4)\n",
      "TIME: 6\n",
      "index: (5, 0)\n",
      "index: (5, 1)\n",
      "index: (5, 2)\n",
      "index: (5, 3)\n",
      "index: (5, 4)\n",
      "index: (5, 5)\n",
      "TIME: 7\n",
      "index: (6, 0)\n",
      "index: (6, 1)\n",
      "index: (6, 2)\n",
      "index: (6, 3)\n",
      "index: (6, 4)\n",
      "index: (6, 5)\n",
      "TIME: 8\n",
      "index: (7, 0)\n",
      "index: (7, 1)\n",
      "index: (7, 2)\n",
      "index: (7, 3)\n",
      "index: (7, 4)\n",
      "index: (7, 5)\n",
      "TIME: 9\n",
      "index: (8, 0)\n",
      "index: (8, 1)\n",
      "index: (8, 2)\n",
      "index: (8, 3)\n",
      "index: (8, 4)\n",
      "index: (8, 5)\n",
      "TIME: 10\n",
      "index: (9, 0)\n",
      "index: (9, 1)\n",
      "index: (9, 2)\n",
      "index: (9, 3)\n",
      "index: (9, 4)\n",
      "index: (9, 5)\n",
      "TIME: 11\n",
      "index: (10, 0)\n",
      "index: (10, 1)\n",
      "index: (10, 2)\n",
      "index: (10, 3)\n",
      "index: (10, 4)\n",
      "index: (10, 5)\n",
      "TIME: 12\n",
      "index: (11, 1)\n",
      "index: (11, 2)\n",
      "index: (11, 3)\n",
      "index: (11, 4)\n",
      "index: (11, 5)\n",
      "TIME: 13\n",
      "index: (12, 2)\n",
      "index: (12, 3)\n",
      "index: (12, 4)\n",
      "index: (12, 5)\n",
      "TIME: 14\n",
      "index: (13, 3)\n",
      "index: (13, 4)\n",
      "index: (13, 5)\n",
      "TIME: 15\n",
      "index: (14, 4)\n",
      "index: (14, 5)\n",
      "TIME: 16\n",
      "index: (15, 5)\n"
     ]
    }
   ],
   "source": [
    "output_grid = decoder.search(start_hyp=start_hyp, constraints=sample_constraints, max_source_len=15, beam_size=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "key: (0, 0) hyp: [(u'<S>', None)]\n",
      "key: (1, 0) hyp: [(u'<S>', None), (6, None)]\n",
      "key: (1, 1) hyp: [(u'<S>', None), (5, (1, 0))]\n",
      "key: (1, 1) hyp: [(u'<S>', None), (1, (0, 0))]\n",
      "key: (2, 0) hyp: [(u'<S>', None), (6, None), (3, None)]\n",
      "key: (2, 1) hyp: [(u'<S>', None), (6, None), (5, (1, 0))]\n",
      "key: (2, 1) hyp: [(u'<S>', None), (6, None), (1, (0, 0))]\n",
      "key: (2, 2) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (2, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (3, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None)]\n",
      "key: (3, 1) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0))]\n",
      "key: (3, 1) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0))]\n",
      "key: (3, 2) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (3, 2) hyp: [(u'<S>', None), (6, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (3, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None)]\n",
      "key: (3, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (3, 3) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (4, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None)]\n",
      "key: (4, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0))]\n",
      "key: (4, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0))]\n",
      "key: (4, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None)]\n",
      "key: (4, 2) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (4, 2) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (4, 2) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None)]\n",
      "key: (4, 3) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (4, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0))]\n",
      "key: (4, 3) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (9, None)]\n",
      "key: (4, 3) hyp: [(u'<S>', None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (4, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (4, 4) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (5, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None)]\n",
      "key: (5, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (5, (1, 0))]\n",
      "key: (5, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (1, (0, 0))]\n",
      "key: (5, 2) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None)]\n",
      "key: (5, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (5, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None)]\n",
      "key: (5, 2) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None)]\n",
      "key: (5, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (5, 3) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (5, 3) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (5, (1, 0))]\n",
      "key: (5, 3) hyp: [(u'<S>', None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None)]\n",
      "key: (5, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (5, (1, 0))]\n",
      "key: (5, 3) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (5, 4) hyp: [(u'<S>', None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (5, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (5, 4) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (5, 4) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (9, None), (1, (0, 0))]\n",
      "key: (5, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (5, 5) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (6, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None)]\n",
      "key: (6, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0))]\n",
      "key: (6, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (5, (1, 0))]\n",
      "key: (6, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (6, 2) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None)]\n",
      "key: (6, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None)]\n",
      "key: (6, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (3, None)]\n",
      "key: (6, 2) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None)]\n",
      "key: (6, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (6, 3) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None)]\n",
      "key: (6, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (5, (1, 0))]\n",
      "key: (6, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (6, 3) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (5, (1, 0))]\n",
      "key: (6, 4) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (6, 4) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (6, 4) hyp: [(u'<S>', None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None), (1, (0, 0))]\n",
      "key: (6, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (6, 4) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (6, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (5, None)]\n",
      "key: (6, 5) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0)), (2, (0, 1)), (3, None)]\n",
      "key: (6, 5) hyp: [(u'<S>', None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (9, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (6, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (6, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (7, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None)]\n",
      "key: (7, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0))]\n",
      "key: (7, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (5, (1, 0))]\n",
      "key: (7, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (7, 2) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, None)]\n",
      "key: (7, 2) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None)]\n",
      "key: (7, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (7, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None)]\n",
      "key: (7, 3) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None)]\n",
      "key: (7, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (3, None), (5, (1, 0))]\n",
      "key: (7, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None)]\n",
      "key: (7, 3) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, (1, 0))]\n",
      "key: (7, 3) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (5, (1, 0))]\n",
      "key: (7, 4) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (1, (0, 0))]\n",
      "key: (7, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (7, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (7, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (7, 4) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (7, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None)]\n",
      "key: (7, 5) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (7, 5) hyp: [(u'<S>', None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (7, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (7, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (8, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None)]\n",
      "key: (8, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (1, (0, 0))]\n",
      "key: (8, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0))]\n",
      "key: (8, 2) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (4, None)]\n",
      "key: (8, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (8, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (8, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None)]\n",
      "key: (8, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None)]\n",
      "key: (8, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (8, 3) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, None), (5, (1, 0))]\n",
      "key: (8, 3) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (3, None)]\n",
      "key: (8, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None)]\n",
      "key: (8, 3) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0))]\n",
      "key: (8, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (3, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (8, 4) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (1, (0, 0))]\n",
      "key: (8, 4) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (8, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, (0, 0))]\n",
      "key: (8, 4) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (8, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (8, None)]\n",
      "key: (8, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (8, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (8, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None)]\n",
      "key: (8, 5) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (9, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None)]\n",
      "key: (9, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0))]\n",
      "key: (9, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0))]\n",
      "key: (9, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (9, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None)]\n",
      "key: (9, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (9, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None)]\n",
      "key: (9, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None)]\n",
      "key: (9, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None)]\n",
      "key: (9, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (5, (1, 0))]\n",
      "key: (9, 3) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (3, None), (2, None)]\n",
      "key: (9, 3) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (4, None), (5, (1, 0))]\n",
      "key: (9, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (5, (1, 0))]\n",
      "key: (9, 4) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (3, None), (1, (0, 0))]\n",
      "key: (9, 4) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (9, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (9, 4) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (9, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (1, (0, 0))]\n",
      "key: (9, 5) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (9, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (9, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (8, None), (8, None)]\n",
      "key: (9, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (1, (0, 0)), (2, (0, 1)), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (9, 5) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (10, 0) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None)]\n",
      "key: (10, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (5, (1, 0))]\n",
      "key: (10, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (1, (0, 0))]\n",
      "key: (10, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None)]\n",
      "key: (10, 2) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (9, None)]\n",
      "key: (10, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (10, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None)]\n",
      "key: (10, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (10, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None)]\n",
      "key: (10, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (10, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (5, (1, 0))]\n",
      "key: (10, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (10, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0))]\n",
      "key: (10, 4) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (3, None), (2, None), (1, (0, 0))]\n",
      "key: (10, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (1, (0, 0))]\n",
      "key: (10, 4) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (4, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (10, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (10, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (10, 5) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (10, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (10, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (10, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, (0, 0)), (2, (0, 1)), (8, None)]\n",
      "key: (10, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (8, None), (8, None), (0, None)]\n",
      "key: (11, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None), (5, (1, 0))]\n",
      "key: (11, 1) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None), (1, (0, 0))]\n",
      "key: (11, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (11, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None), (5, None)]\n",
      "key: (11, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (11, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None)]\n",
      "key: (11, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1)), (3, None)]\n",
      "key: (11, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (2, None)]\n",
      "key: (11, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None)]\n",
      "key: (11, 3) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (9, None), (5, (1, 0))]\n",
      "key: (11, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (11, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (5, (1, 0))]\n",
      "key: (11, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (1, (0, 0))]\n",
      "key: (11, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (11, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (11, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (11, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (11, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (11, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (8, None), (8, None), (0, None), (8, None)]\n",
      "key: (11, 5) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (7, None)]\n",
      "key: (11, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None)]\n",
      "key: (11, 5) hyp: [(u'<S>', None), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (7, None), (3, None), (2, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (12, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (12, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1)), (3, None), (8, None)]\n",
      "key: (12, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (12, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None), (5, None), (0, None)]\n",
      "key: (12, 2) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None), (0, None)]\n",
      "key: (12, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1)), (3, None), (5, (1, 0))]\n",
      "key: (12, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None), (5, (1, 0))]\n",
      "key: (12, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (12, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None)]\n",
      "key: (12, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None), (5, None), (5, (1, 0))]\n",
      "key: (12, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (1, (0, 0))]\n",
      "key: (12, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (2, None), (1, (0, 0))]\n",
      "key: (12, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (12, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (12, 4) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (9, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (12, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None), (2, None)]\n",
      "key: (12, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (12, 5) hyp: [(u'<S>', None), (6, None), (3, None), (1, (0, 0)), (2, (0, 1)), (0, None), (4, None), (5, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (7, None), (1, None)]\n",
      "key: (12, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (12, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (13, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None), (0, None), (5, (1, 0))]\n",
      "key: (13, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1)), (3, None), (8, None), (5, (1, 0))]\n",
      "key: (13, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None), (0, None)]\n",
      "key: (13, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None), (5, None), (0, None), (5, (1, 0))]\n",
      "key: (13, 3) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0))]\n",
      "key: (13, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (1, (0, 0))]\n",
      "key: (13, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (13, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1)), (3, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (13, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None), (5, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (13, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None), (1, (0, 0))]\n",
      "key: (13, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (2, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (13, 5) hyp: [(u'<S>', None), (1, (0, 0)), (2, (0, 1)), (6, None), (9, None), (1, None), (6, None), (0, None), (5, None), (2, None), (9, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (13, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (13, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (13, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None), (2, None), (0, None)]\n",
      "key: (14, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (0, None), (0, None), (1, (0, 0)), (2, (0, 1)), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (14, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (1, (0, 0)), (2, (0, 1)), (3, None), (8, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (14, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (1, (0, 0)), (2, (0, 1)), (7, None), (6, None), (3, None), (5, None), (0, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (14, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1))]\n",
      "key: (14, 4) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None), (0, None), (1, (0, 0))]\n",
      "key: (14, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None)]\n",
      "key: (14, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (2, None), (1, (0, 0)), (2, (0, 1)), (9, None)]\n",
      "key: (14, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (14, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None)]\n",
      "key: (14, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None), (2, None), (0, None), (7, None)]\n",
      "key: (15, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None), (1, (0, 0)), (2, (0, 1)), (4, None)]\n",
      "key: (15, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (1, (0, 0)), (2, (0, 1)), (6, None), (3, None), (2, None), (0, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2))]\n",
      "key: (15, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (7, None), (8, None), (2, None), (0, None), (4, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (4, None), (0, None), (1, (0, 0)), (2, (0, 1))]\n",
      "key: (15, 5) hyp: [(u'<S>', None), (6, None), (3, None), (7, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (0, None), (1, None), (7, None), (0, None), (2, None), (1, (0, 0)), (2, (0, 1)), (9, None), (6, None)]\n",
      "key: (15, 5) hyp: [(u'<S>', None), (6, None), (1, (0, 0)), (2, (0, 1)), (2, None), (2, None), (9, None), (6, None), (5, (1, 0)), (6, (1, 1)), (7, (1, 2)), (3, None), (2, None), (0, None), (7, None), (9, None)]\n"
     ]
    }
   ],
   "source": [
    "[k for k in output_grid]\n",
    "for k in output_grid:\n",
    "    for hyp in output_grid[k]:\n",
    "        print('key: {} hyp: {}'.format(k, hyp.sequence))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "66"
      ]
     },
     "execution_count": 39,
     "output_type": "execute_result",
     "metadata": {}
    }
   ],
   "source": [
    "len(output_grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_hyps = dumb_tm.dumb_generate(start_hyp, n_best=N_BEST)\n",
    "next_new_constraint_hyps = dumb_tm.dumb_generate_from_constraints(start_hyp)\n",
    "len(next_new_constraint_hyps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_continued_constraint_hyps = [dumb_tm.dumb_continue_unfinished_constraint(hyp)\n",
    "                                  for hyp in next_new_constraint_hyps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(next_continued_constraint_hyps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(next_continued_constraint_hyps[1].unfinished_constraint)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(next_new_constraint_hyps[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next_next_hyps = [dumb_tm.dumb_generate(h, n_best=N_BEST) for h in next_hyps]\n",
    "next_next_hyps = [h for s in next_next_hyps for h in s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(next_next_hyps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[h.sequence for h in next_next_hyps]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(next_hyps[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#     def __init__(self, token, score, coverage, constraints, payload=None, backpointer=None,\n",
    "#                  unfinished_constraint=False):\n",
    "start_hyp ="
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_hyp(previous_hyp, next_token=None, constraint_idx=None, constraint_token_idx=None)\n",
    "    \"\"\"Utility function to create a hypothesis in different ways\"\"\"\n",
    "    pass"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}